package leetCode.hw.math;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class HJ5Solution implements HJ5{

    /**
     * 所有的质数因子求解
     * @param num
     * @return
     */
    @Override
    public String allPrimeNum(int num) {
        StringBuilder result = new StringBuilder();
        if(num==1) return result.toString();
        for(int i=2;i<=Math.sqrt(num);i++) {
            while (num % i==0){
                result.append(i).append(" ");
                num/=i;
            }
        }
        if(num!=1) result.append(num);
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(new HJ5Solution().allPrimeNum(180));
    }

    /**
     * 普通解法,会超时！！
     * @param num
     * @return
     */
    public static List<Integer> getAllPrimeFactor(long num) {
        List<Integer> result = new ArrayList<>();
        if (num == 1) return result;
        while(num>1) {
            for(int i=2;i<=num;i++) {
                // 如果能除尽，判断该数是否是质数
                if(num%i==0){
                    boolean is = true;
                    for(int j=2;j<=(int)Math.sqrt(i);j++){
                        if (i % j == 0) {
                            is = false;
                            break;
                        }
                    }
                    if(is){
                        result.add(i);
                        num/=i;
                    }
                }
            }
        }
        result.sort(Comparator.comparingInt(o -> o));
        return result;
    }

}
